import java.util.*;

public class Solution957 {
    public int[] prisonAfterNDays(int[] cells, int n) {
        List<Integer> list=new ArrayList<>();
        Map<Integer,Integer> map=new HashMap<>();
        map.put(cal(cells),0);
        list.add(cal(cells));
        int cur=0;
        while (true){
            cells=update(cells);
            cur++;
            if (n==cur){
                return cells;
            }
            if (map.containsKey(cal(cells))){
                return toArray(list.get((n-map.get(cal(cells)))%(cur-map.get(cal(cells)))+map.get(cal(cells))));
            }else{
                list.add(cal(cells));
                map.put(cal(cells),cur);
            }
        }
    }

    private int[] toArray(int t) {
        int[] ans=new int[8];
        for (int i=7;i>=0;i--){
            ans[i]=t%2;
            t/=2;
        }
        return ans;
    }

    private int[] update(int[] cells) {
        int[] newCells=new int[cells.length];
        for (int i=1;i<cells.length-1;i++){
            if (cells[i-1]==cells[i+1]){
                newCells[i]=1;
            }
        }
        return newCells;
    }

    private Integer cal(int[] cells) {
        int t=0;
        for (int cell : cells) {
            t=t*2+cell;
        }
        return t;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution957().prisonAfterNDays(new int[]{1, 0, 0, 1, 0, 0, 1, 0}, 1000000000)));
    }
}
